#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<unordered_set>
using namespace std;

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size(), L = 1, start = 0;
        for (int i = 0; i < n; ++i)
        {
            int left = i - 1, right = i + 1;
            while (left >= 0 && right < n && s[left] == s[right])
                --left, ++right;
            if (right - left - 1 > L)
            {
                L = right - left - 1;
                start = left + 1;
            }
            left = i, right = i + 1;
            while (left >= 0 && right < n && s[left] == s[right]) --left, ++right;
            if (right - left - 1 > L)
            {
                L = right - left - 1;
                start = left + 1;
            }
        }
        return s.substr(start, L);
    }

    int crossRiver(int n, int m, int x, int y) {
        vector<vector<int>> dp(n + 2, vector<int>(m + 2));
        dp[0][1] = 1;
        x += 1, y += 1;
        for (int i = 1; i <= n + 1; ++i)
        {
            for (int j = 1; j <= m + 1; ++j)
            {
                if (i != x && y != j && abs(i - x) + abs(j - y) == 3 || (x == i && y == j)) dp[i][j] = 0;
                else dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[n + 1][m + 1];
    }

    int gcd(int a, int b)
    {
        if (b == 0) return a;
        return gcd(b, a % b);
    }

    int lcm(int a,int b)
    {
        return a * b / gcd(a, b);
    }

    void triangle()
    {
        int n;
        cin >> n;
        while (n--)
        {
            vector<int> t(6);
            for (int i = 0; i < 6; ++i) cin >> t[i];
            sort(t.begin(), t.end());
            if ((t[0] + t[1] > t[2] && t[3] + t[4] > t[5])
                || (t[0] + t[2] > t[3] && t[1] + t[4] > t[5])
                || (t[0] + t[3] > t[4] && t[2] + t[1] > t[5])
                || (t[0] + t[4] > t[5] && t[1] + t[2] > t[3]))
                cout << "Yes" << endl;
            else cout << "No" << endl;
        }

    }
    int MLS(vector<int>& arr) {
        int n = arr.size();
        sort(arr.begin(), arr.end());
        int ans = 0;
        for (int i = 0; i < n;)
        {
            int j = i + 1, count = 1;
            while (j < n)
            {
                if (arr[j] - arr[j - 1] == 1)
                {
                    ++j; ++count;
                }
                else if (arr[j] - arr[j - 1] == 0)
                {
                    ++j;
                }
                else
                {
                    break;
                }
            }
            ans = max(ans, count);
            i = j;
        }
        return ans;
    }

    int dir[4][2] = { {1,0},{0,1},{-1,0},{0,-1} };
    bool visited[210][210] = { 0 };
    int m, n;
    int solve(vector<vector<char> >& grid)
    {
        int ret = 0;
        m = grid.size(), n = grid[0].size();
        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (grid[i][j] == '1' && !visited[i][j])
                {
                    ++ret;
                    dfs(grid, i, j);
                }
            }
        }
        return ret;
    }

    void dfs(vector<vector<char> >& grid, int i, int j)
    {
        visited[i][j] = true;
        for (int k = 0; k < 4; ++k)
        {
            int x = i + dir[k][0], y = j + dir[k][1];
            if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1' && !visited[x][y])
                dfs(grid, x, y);
        }
    }

    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int mx = INT_MIN;
        priority_queue<pair<int, int>> q;
        vector<int> ans;
        for (int i = 0; i < k; ++i)
            q.emplace(nums[i], i);
        ans.push_back(q.top().first);
        for (int i = k; i < nums.size(); ++i)
        {
            q.emplace(nums[i], i);
            while (q.top().second <= i - k)
                q.pop();
            ans.push_back(q.top().first);
        }
        return ans;
    }

    int longestConsecutive(vector<int>& nums) {
        int n = nums.size();
        unordered_set<int> s;
        for (int num : nums)
            s.insert(num);
        int ans = 0, cur = 0, curNum = 0;
        for (int x : s)
        {
            if (!s.count(x - 1))
            {
                curNum = x;
                cur = 1;
                while (s.count(curNum + 1))
                {
                    ++curNum;
                    ++cur;
                }
            }
            ans = max(ans, cur);
        }
        return ans;
    }
};